package jm.algorithm.sort;

/**
 * @Description 自定义对象计数排序
 * @date 2022/5/8 15:58
 */
public class CountingSortObj{

    public static void main(String[] args) {
        Person[] arr = {new Person(1,"aa")
                ,new Person(-1,"bb"),
                new Person(99,"cc"),
                new Person(5,"dd"),
                new Person(0,"ee"),};
        sort(arr);
        for (Person person : arr) {
            System.out.println(person);
        }
    }

    private static void sort(Person[] arr) {
        // 获取数组最大值
        int max = arr[0].getId();
        int min = arr[0].getId();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].getId() > max){
                max = arr[i].getId();
            }
            if (arr[i].getId() < min){
                min = arr[i].getId();
            }
        }

        // 开辟内存空间
        int[] counts = new int[max - min + 1];

        // 统计次数
        for (Person person : arr) {
            counts[person.getId() - min]++;
        }

        // 统计累加的次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 倒序遍历然后将值放到合适位置
        Person[] newArr = new Person[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将当前值根据在counts中的索引计算出新的位置。
            // 先将值减一，在计算出当前值对应的索引
            int index = --counts[arr[i].getId() - min];
            // 放到新序列中。
            newArr[index] = arr[i];
        }

        // 覆盖序列
        System.arraycopy(newArr, 0, arr, 0, newArr.length);
    }
}
